package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: combinationSum
 * @author: chanzhugang
 * @create: 2022/08/19 15:03
 */
public class CombinationSum {

    /**
     * 39 组合总和
     *
     * @param candidates
     * @param target
     * @return
     */
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 数组中无重复元素， 一个数字可以无限制重复选取
        backtrack(candidates, 0, target, new ArrayList<>());
        return result;
    }

    /**
     * @param candidates
     * @param k          阶段
     * @param left       剩多少满足条件
     * @param path       路径
     */
    private void backtrack(int[] candidates, int k, int left, List<Integer> path) {
        if (left == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (k == candidates.length) {
            return;
        }

        for (int i = 0; i <= left / candidates[k]; i++) {
            // 一个值可以用多次
            for (int j = 0; j < i; j++) {
                path.add(candidates[k]);
            }

            backtrack(candidates, k + 1, left - i * candidates[k], path);
            // 撤销
            for (int j = 0; j < i; j++) {
                path.remove(path.size() - 1);
            }
        }
    }
}